package com.liunian.algorithmstudy.tree;

public class BuildTree106 extends TreeNode {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		int postLen = postorder.length;
		int inLen = inorder.length;
		if (postLen == 0) {
			return null;
		}
		TreeNode root = new TreeNode(postorder[postLen - 1]);
		int index = 0;
		for (int i = 0; i < inLen; i++) {
			if (inorder[i] == postorder[postLen - 1]) {
				index = i;
				break;
			}
		}
		int[] inorderLeft = processNums(inorder, 0, index);
		int[] inorderRight = processNums(inorder, index + 1, inLen);
		int[] postorderLeft = processNums(postorder, 0, inorderLeft.length);
		int[] postorderRight = processNums(postorder, inorderLeft.length, postLen - 1);
		TreeNode leftTree = buildTree(inorderLeft, postorderLeft);
		TreeNode rightTree = buildTree(inorderRight, postorderRight);
		root.left = leftTree;
		root.right = rightTree;
		return root;
	}

	private int[] processNums(int[] nums, int from, int to) {
		int[] res = new int[to - from];
		for (int i = 0; i < to - from; i++) {
			res[i] = nums[from + i];
		}
		return res;
	}

	public static void main(String[] args) {
		BuildTree106 buildTree = new BuildTree106();
		buildTree.buildTree(new int[]{2,1}, new int[]{1,2});
	}

}
